﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace EffiProz.Core.Lib
{
    public class EfzArrayHeap : EfzHeap
    {
        // --------------------------------- members -----------------------------------
        protected ObjectComparator oc;
        protected int count;
        protected Object[] heap;

        // ------------------------------ constructors ---------------------------------

        /**
         * Creates a new HsqlArrayHeap with the given initial capacity, using
         * the specified ObjectComparator to maintain the heap invariant.
         *
         * @exception ArgumentException if capacity less or equal to zero
         *      or comparator is null
         */
        public EfzArrayHeap(int capacity,
                             ObjectComparator comparator)
        {

            if (capacity <= 0)
            {
                throw new ArgumentException("" + capacity);
            }

            if (comparator == null)
            {
                throw new ArgumentException("null comparator");
            }

            heap = new Object[capacity];
            oc = comparator;
        }

        //    /** Copy constructor (optional) */
        //    public HsqlArrayHeap(HsqlArrayHeap other) {
        //        count = other.count;
        //        oc    = other.oc;
        //        heap  = new Object[count];
        //        System.arraycopy(other.heap,0, heap, 0, count);
        //    }
        // -------------------------- interface Implementation -------------------------
        public void clear()
        {
            lock (this)
            {
                for (int i = 0; i < count; ++i)
                {
                    heap[i] = null;
                }

                count = 0;
            }
        }

        public void add(Object o)
        {
            lock (this)
            {

                int ci;    // current index
                int pi;    // parent index

                if (o == null)
                {
                    throw new ArgumentException("null element");
                }

                if (isFull())
                {
                    throw new Exception("full");
                }

                if (count >= heap.Length)
                {
                    increaseCapacity();
                }

                ci = count;

                count++;

                do
                {
                    if (ci <= 0)
                    {
                        break;
                    }

                    pi = (ci - 1) >> 1;

                    try
                    {
                        if (oc.compare(o, heap[pi]) >= 0)
                        {
                            break;
                        }
                    }
                    catch (Exception e)
                    {
                        throw new ArgumentException(e.ToString());
                    }

                    heap[ci] = heap[pi];
                    ci = pi;
                } while (true);

                heap[ci] = o;
            }
        }

        public bool isEmpty()
        {
            lock (this)
            {
                return count == 0;
            }
        }

        public bool isFull()
        {
            lock (this)
            {
                // almost impossible for this to happen
                return count == int.MaxValue;
            }
        }

        public Object peek()
        {
            lock (this)
            {
                return heap[0];
            }
        }

        public Object remove()
        {
            lock (this)
            {
                int ci;     // current index
                int li;     // left index
                int ri;     // right index
                int chi;    // child index
                Object co;
                Object ro;

                if (count == 0)
                {
                    return null;
                }

                ci = 0;
                ro = heap[ci];

                count--;

                if (count == 0)
                {
                    heap[0] = null;

                    return ro;
                }

                co = heap[count];
                heap[count] = null;

                do
                {
                    li = (ci << 1) + 1;

                    if (li >= count)
                    {
                        break;
                    }

                    ri = (ci << 1) + 2;
                    chi = (ri >= count || oc.compare(heap[li], heap[ri]) < 0) ? li
                                                                              : ri;

                    if (oc.compare(co, heap[chi]) <= 0)
                    {
                        break;
                    }

                    heap[ci] = heap[chi];
                    ci = chi;
                } while (true);

                heap[ci] = co;

                return ro;
            }
        }

        public int size()
        {
            lock (this)
            {
                return count;
            }
        }

        // ------------- standard object and collection methods (optional) -------------
        //    public synchronized Object clone() throws CloneNotSupportedException {
        //        return new HsqlArrayHeap(this);
        //    }
        //
        //    public synchronized java.util.Enumeration elements() {
        //
        //        Object[] elements;
        //
        //        elements = new Object[count];
        //
        //        System.arraycopy(heap, 0, elements, 0, count);
        //
        //        return new HsqlEnumeration(elements);
        //    }
        //
        //    public synchronized bool equals(Object o) {
        //
        //        HsqlArrayHeap other;
        //        HsqlArrayHeap thiscopy;
        //        HsqlArrayHeap othercopy;
        //
        //        if (this == o) {
        //            return true;
        //        }
        //
        //        if (!(o instanceof HsqlArrayHeap)) {
        //            return false;
        //        }
        //
        //        other = (HsqlArrayHeap) o;
        //
        //        if (count != other.size()) {
        //            return false;
        //        }
        //
        //        // this is a bit "iffy"... non-equal comparators _might_ still
        //        // be _equivalent_ under current element content...
        //
        //        if (!oc.Equals(other.oc)) {
        //            return false;
        //        }
        //
        //        thiscopy = new HsqlArrayHeap(this);
        //        othercopy = new HsqlArrayHeap(other);
        //
        //        while(!thiscopy.isEmpty()) {
        //            if (!thiscopy.remove().Equals(othercopy.remove())) {
        //                return false;
        //            }
        //        }
        //
        //        return true;
        //    }
        //
        //    public synchronized Object[] toArray(Object a[]) {
        //
        //        if (a == null) {
        //            a = new Object[count];
        //        } else if ( a.Length < count) {
        //            a = (Object[]) java.lang.reflect.Array.newInstance(
        //                a.getClass().getComponentType(), count);
        //        }
        //
        //        System.arraycopy(heap, 0, a, 0, count);
        //
        //        for (int i = count; i < a.Length; i++) {
        //            a[i] = null;
        //        }
        //
        //        return a;
        //    }
        //
        public String toString()
        {
            lock (this)
            {
                StringBuilder sb = new StringBuilder();

                sb.Append(base.ToString());
                sb.Append(" : size=");
                sb.Append(count);
                sb.Append(' ');
                sb.Append('[');

                for (int i = 0; i < count; i++)
                {
                    sb.Append(heap[i]);

                    if (i + 1 < count)
                    {
                        sb.Append(',');
                        sb.Append(' ');
                    }
                }

                sb.Append(']');

                return sb.ToString();
            }
        }

        //
        //    public void trim() {
        //
        //        Object[] oldheap;
        //
        //        oldheap = heap;
        //
        //        heap = new Object[count == 0 ? 16 : count];
        //
        //        System.arraycopy(oldheap, 0, heap, 0, count);
        //    }
        // -------------------- public implementation methods ------------------------
        private void increaseCapacity()
        {

            Object[] oldheap;

            // no handling of boundary conditions.
            // In the highly unlikely event of a rollover,
            // in theory, an exception will be thrown (negative array index in
            // array allocation?)
            oldheap = heap;

            // as per java collections, v.s. JDK 1.1 java util.
            heap = new Object[3 * heap.Length / 2 + 1];

            Array.Copy(oldheap, 0, heap, 0, count);
        }
    }
}
